#include <string.h>
#include <malloc.h>

#define ALPHASIZ 128
#define FALSE 0
#define TRUE 1
#define MAX(a, b) ((a)>(b)?(a):(b))

typedef struct bm_pattern	//boyer-moore pattern 
{
    short p_m;			//length of pattern string
    short p_r[ALPHASIZ];	//'r' vector
    short *p_R;			//'R' vector
    char *p_pat;		//pattern string
} BM_PATTERN;

char *bm_pmatch(BM_PATTERN *, char *);
BM_PATTERN *bm_makepat(char *);
void bm_freepat(BM_PATTERN *);

/*
 *BM_MAKEPAT-make a boyer-moore pattern.
 */

BM_PATTERN *bm_makepat(char *p)
{
    register int i, j, k, l;
    short m;
    short *r, *R;
    char *s;
    int unify;
    BM_PATTERN *pat;

    pat = (BM_PATTERN *) calloc(1, sizeof(BM_PATTERN));
    if (!pat)
	return (NULL);
    pat->p_m = strlen(p);	//string length
    if (!(pat->p_pat = strdup(p))) {
	free(pat);
	return (NULL);
    }

    pat->p_R = (short *) calloc(pat->p_m + 1, sizeof(short));
    r = pat->p_r;
    R = pat->p_R;
    m = pat->p_m;

    if (!R) {
	free(pat->p_pat);
	free(pat);
	return (NULL);
    }

    for (i = 0; i < ALPHASIZ; ++i)	//compute 'r'-:word alphas
	if (s = strrchr(p, i))
	    r[i] = m - (s - p) - 1;
	else
	    r[i] = m;
    for (j = 0; j < m; ++j) {	//compute 'R'
	k = j;			//set maxinum k
	while (1) {
	    //look for unification
	    if ((k > 0) && (p[k - 1] == p[j])) {
		--k;
		continue;
	    }

	    l = k + m - j - 1;
	    i = m - 1;
	    unify = FALSE;

	    while (1) {		//test one possibility
		if ((i == j) || (l < 1)) {
		    unify = TRUE;
		    break;
		} else if (p[i] != p[l]) {
		    unify = FALSE;
		    break;
		} else {
		    (--i, --l);
		}
	    }
	    if (unify = TRUE) {	//did unify pattern
		R[j] = m - k;
		break;
	    } else {		//failed, decrement and go on
		--k;
		continue;
	    }
	}			//end of loop
    }				//end of for
    return (pat);
}

/*
 *BM_PMATCH-look for a pattern in given string.
 */
char *bm_pmatch(BM_PATTERN * pat, register char *s)
{
    register short i, j, n;
    short m;
    short *r, *R;
    char *p;			//ptr to pattern 'p'
    char *S;			//ptr to start of 's'
    char *Pend;			//ptr to end of pattern

    n = strlen(s);		//initialize
    p = pat->p_pat;
    r = pat->p_r;
    R = pat->p_R;
    m = pat->p_m;
    i = m - 1;
    S = s;
    Pend = &(pat->p_pat[i]);	//last element of pattern
    s = &S[i];

    while (1) {
	if (i >= n)		//failure:pattern's lenght bigger than source's
	    return (NULL);
	else			//restart
	    (j = m - 1, p = Pend);
	while (1) {
#if _DEBUG
	    printf("S(i: %d): '%c', P(j: %d): '%c'\n", i, s[i], j, p[j]);
#endif
	    if (j == (-1))	//success
		return (s);
	    if (*s == *p) {
		//compare
		(--j, --i);
		(--s, --p);
	    } else {
		//advance i
//#if _DEBUG
//                printf("S(i: %d): '%c', P(j: %d): '%c'\n", i, s[i], j, p[j]);
//#endif
		i += MAX(R[j], r[*s]);	//two jump table
		s = &S[i];
		break;
	    }
	}			//end of loop
    }				//end of loop
}

/*
 *BM_FREEPAT-free a Boyer-Moore pattern.
 */
void bm_freepat(BM_PATTERN * pattern)
{
    free(pattern->p_pat);
    free((char *) pattern->p_R);
    free((char *) pattern);
    return;
}

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char *argv[])
{
    char buf[BUFSIZ];
    int lineno;
    BM_PATTERN *pat;

    pat = bm_makepat(argv[1]);
    lineno = 1;
    while (fgets(buf, BUFSIZ, stdin)) {
	if (bm_pmatch(pat, buf))
	    printf("%d: %s\n", lineno, buf);
	++lineno;
    }
    exit(0);
    // return 0;
}
